/*
 * @lc app=leetcode.cn id=743 lang=typescript
 *
 * [743] 网络延迟时间
 */

// @lc code=start
function networkDelayTime(times: number[][], n: number, k: number): number {
  const graph = new Array(n).fill(0).map((_) => new Array(n).fill(Number.POSITIVE_INFINITY));
  // 建模
  for (let [from, to, time] of times) {
    graph[from - 1][to - 1] = time;
  }

  const visited = new Array(n).fill(0);
  const dist = new Array(n).fill(Number.POSITIVE_INFINITY);
  dist[k - 1] = 0;

  for (let i = 0; i < n; i++) {
    let x = -1;
    // 先找到最小的顶点
    for (let y = 0; y < n; y++) {
      if (!visited[y] && (x === -1 || dist[y] < dist[x])) {
        x = y;
      }
    }
    visited[x] = 1;
    // 更新所有跟最小顶点连接的点的边的权重
    for (let y = 0; y < n; y++) {
      dist[y] = Math.min(dist[y], dist[x] + graph[x][y]);
    }
  }
  // 所有最小边中的最大值
  const ans = Math.max(...dist);

  return isFinite(ans) ? ans : -1;
}
// @lc code=end
